package com.learn.algo.dp;

import org.junit.Test;

/**
 * <pre>
 * 动态规划：0-1背包问题
 * 题目：
 * 给定n个物品，第i个物品的重量为wgt[i-1]，价值为val[i-1]，现在有一个容量为cap的背包，每个物品只能
 * 选择一次，问在不超过背包容量的情况下物品的最大价值。
 * 注意：
 * 物品编号i从1开始，数组索引从0开始，所以物品i对应的重量为wgt[i-1]，价值为val[i-1]
 * </pre>
 */
public class Knapsack_01 {

    @Test
    public void test() {
        int[] wgt = new int[]{1, 2, 3};
        int[] val = new int[]{5, 11, 15};
        int cap = 4;
        System.out.println(solve(wgt, val, cap));
        System.out.println(solveByStatusCompress(wgt, val, cap));
    }

    /**
     * 求解
     * 二维数组：横轴 - 容量；竖轴：价值
     *
     * @param wgt 重量数组
     * @param val 价值数组
     * @param cap 容量
     * @return int
     */
    public int solve(int[] wgt, int[] val, int cap) {
        int n = wgt.length;
        // 初始化dp数据
        int[][] dp = new int[n + 1][cap + 1];
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= cap; j++) {
                if (wgt[i - 1] > j) {
                    // 如果超过背包容量，则不选择物品
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 在不选物品和选择物品之间取价值最大的选项
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n][cap];
    }


    /**
     * 求解 - 状态压缩
     * 使用一维数组，倒序遍历求解。每次复写该数组即可
     *
     * @param wgt 重量数组
     * @param val 价值数组
     * @param cap 容量
     * @return int
     */
    public int solveByStatusCompress(int[] wgt, int[] val, int cap) {
        int n = wgt.length;
        // 初始化dp数据：一维数组标识，下标为容量
        int[] dp = new int[cap + 1];
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = cap; j >= 1; j--) {
                if (wgt[i - 1] > j) {
                    // 如果超过背包容量，则不选择物品
                    // 不改变
                } else {
                    // 在不选物品和选择物品之间取价值最大的选项
                    dp[j] = Math.max(dp[j], dp[j - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }
}


